import java.util.ArrayList;
import java.util.List;

/**
 * 1749. 任意子数组和的绝对值的最大值
 * https://leetcode-cn.com/problems/maximum-absolute-sum-of-any-subarray/
 */
public class Solutions_1749 {
    public static void main(String[] args) {
        int[] nums1 = {1, -3, 2, 3, -4};  // output: 5
        int[] nums2 = {2, -5, 1, -4, 3, -2};  // output: 8

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);

        for (int[] input : inputs) {
            int result = maxAbsoluteSum(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：前缀和
     * 维护一个左侧的最大前缀和、最小前缀和
     */
    public static int maxAbsoluteSum(int[] nums) {
        int max = 0, min = 0, ans = 0;
        int preSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 累加前缀和
            preSum += nums[i];
            // 计算得到最大的绝对值子数组和：由当前前缀和
            ans = Math.max(ans, Math.abs(preSum - max));
            ans = Math.max(ans, Math.abs(preSum - min));
            // 更新最大、最小前缀和
            max = Math.max(max, preSum);
            min = Math.min(min, preSum);
        }
        return ans;
    }
}
